package com.github.hgkmail.hello.leetcode101.dp.oned;

public class LC5LongestPalindromicSubstring {
    //暴力法 中心扩展
    public String longestPalindrome(String s) {
        char[] chars=s.toCharArray();
        int len=chars.length;
        if (len<=0) {
            return "";
        }
        int l,r,maxLen=1;
        String maxStr=s.substring(0, 1); //默认最长回文是第一个字符
        //奇数回文串
        for (int i = 0; i < len; i++) {
            l=r=i;
            while (l>=0 && r<len && chars[l]==chars[r]) {
                l--;
                r++;
            }
            l=l+1;
            r=r-1;
            if (r-l+1>maxLen) {
                maxLen=r-l+1;
                maxStr=s.substring(l, r+1);
            }
        }
        //偶数回文串
        for (int i = 1; i < len; i++) {
            l=i-1;
            r=i;
            while (l>=0 && r<len && chars[l]==chars[r]) {
                l--;
                r++;
            }
            l=l+1;
            r=r-1;
            if (r-l+1>maxLen) {
                maxLen=r-l+1;
                maxStr=s.substring(l, r+1);
            }
        }
        return maxStr;
    }

    //todo 动态规划 先枚举子串长度，再枚举左边界
    //如果chars[i]==chars[j], dp[i][j]=dp[i+1][j-1]+1，i、j分别是左右边界
    public String longestPalindrome2(String s) {
        return "";
    }

    public static void main(String[] args) {
        System.out.println(new LC5LongestPalindromicSubstring().longestPalindrome("cbbd"));
    }
}
